---
title: "拼接"
created: 2025-11-28
tags:
  - 算法
---

# 拼接

## 题目 [拼接](https://www.lanqiao.cn/paper/3845/problem/815/)

![[image-e65330ce.png]]

## 思路分析

暂时没有头绪 什么才算能拼成呢 还得旋转

啧 这题主要是卡在了思路上 多模拟下案例会发现和方格分割很像

![[image-db308557.png]]

由于要将矩阵分割成两部分，且旋转后依旧要完美匹配；

因此被分割的两块都必须是沿着主对角线对称的！！！

对于这一点 可以多画几组图

![[image-ca8759a8.png]]

对于找规律的题 要大胆猜测 多画图

案例都不模拟 你怎么找到规律？

那么问题就转变成了——以对角线上的每一个点为起点，在搜索的过程中同时标记搜索点和对称点，当触及边界时，就完成了一次分割；

![[image-09aa42bf.png]]

从之前的中心对称 变成了 对角线对称

左边的上对应对称的右

右对应上

下对应左

左对应下

即 ab对应ba

![[image-409ed927.png]]

ok 接下来就和方格分割一样了 dfs解决

另外要注意的一点是 不能走对角线 也不能跨对角线 所以只有到左边界或到上边界才表示停止 并没有到右下边界停止的情况

![[image-1e9925b1.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=10;

int cnt=0;

bool st[N][N];

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=7 && y>=0 && y<=7 && !st[x][y];

}

void dfs(int x,int y){

	if(x==0 || y==7){

		cnt++;

		return;

	}

	for(int i=0;i<4;i++){

		int nx=x+dx[i],ny=y+dy[i];

		if(isVaild(nx,ny) && isVaild(ny,nx) && nx!=ny){

			st[nx][ny]=st[ny][nx]=true;

			dfs(nx,ny);

			st[nx][ny]=st[ny][nx]=false;

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	for(int i=0;i<=7;i++)

	{

		st[i][i]=true;

		dfs(i,i);

		st[i][i]=false;

	}

	cout<<cnt;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[质数拆分|质数拆分]] 🏠 [[00-冲刺国赛]] ➡️ [[求值|求值]]